BinaryHeap: An Implicit Binary Tree

Heap overview#

Here, we discuss two implementations of the extremely useful priority Queue data structure. Both of these structures are a special kind of binary tree called a heap, which means “a disorganized pile.” This is in contrast to binary search trees that can be thought of as a highly organized pile.

The first heap implementation uses an array to simulate a complete binary tree. This very fast implementation is the basis of one of the fastest known sorting algorithms, namely heapsort. The second implementation is based on more flexible binary trees. It supports a meld(h) operation that allows the priority queue to absorb the elements of a second priority queue h.

BinaryHeap: An implicit binary tree#

Our first implementation of a (priority) Queue is based on a technique that is over four hundred years old. Eytzinger’s method allows us to represent a complete binary tree as an array by laying out the nodes of the tree in breadth-first order. In this way, the root is stored at position $0$, the root’s left child is stored at position $1$, the root’s right child at position $2$, the left child of the left child of the root is stored at position $3$, and so on.

If we apply Eytzinger’s method to a sufficiently large tree, some patterns emerge. The left child of the node at index i is at index left(i) = 2i + 1 and the right child of the node at index i is at index right(i) = 2i+ 2. The parent of the node at index i is at index parent(i) = (i − 1)/2.

A BinaryHeap uses this technique to implicitly represent a complete binary tree in which the elements are heap-ordered: The value stored at any index i is not smaller than the value stored at index parent(i), with the exception of the root value, i = 0. It follows that the smallest value in the priority Queue is therefore stored at position $0$ (the root).

In a BinaryHeap, the n elements are stored in an array a:

The add() operation#

Implementing the add(x) operation is fairly straightforward. As with all array-based structures, we first check to see if a is full (by checking if a.length = n) and, if so, we grow a. Next, we place x at location a[n] and increment n. At this point, all that remains is to ensure that we maintain the heap property. We do this by repeatedly swapping x with its parent until x is no longer smaller than its parent.

The implementation of the add() method:

The remove() operation#

Implementing the remove() operation, which removes the smallest value from the heap, is a little trickier. We know where the smallest value is (at the root), but we need to replace it after we remove it and ensure that we maintain the heap property.

The easiest way to do this is to replace the root with the value a[n − 1], delete that value, and decrement n. Unfortunately, the new root element is now probably not the smallest element, so it needs to be moved downwards. We do this by repeatedly comparing this element to its two children. If it is the smallest of the three then we are done. Otherwise, we swap this element with the smallest of its two children and continue.

The implementation of the remove() method:

As with other array-based structures, we will ignore the time spent in calls to resize(), since these can be accounted for using the amortization argument. The running times of both add(x) and remove() then depend on the height of the (implicit) binary tree. Luckily, this is a complete binary tree; every level except the last has the maximum possible number of nodes. Therefore, if the height of this tree is h, then it has at least $2^h$ nodes. Stated another way

$$n\ge 2^{h}$$

Taking logarithms on both sides of this equation gives

$$h\leq \log n$$

Therefore, both the add(x) and remove() operations run in $O(\log n)$ time.

Summary#

The following theorem summarizes the performance of a BinaryHeap:

Theorem: A BinaryHeap implements the (priority) Queue interface. Ignoring the cost of calls to resize(), a BinaryHeap supports the operations add(x) and remove() in $O(\log n)$ time per operation.

Furthermore, beginning with an empty BinaryHeap, any sequence of $m$ add(x) and remove() operations results in a total of $O(m)$ time spent during all calls to resize().

Explanation

Let’s start our explanation from the start of main().

• Line 93: It creates a new binary heap data structure instance h with Integer values.
• Line 95: It creates a new instance r of a Random object that will be used to generate random values.
• Lines 100–101: This loop adds n random values to the heap using the add() method.
• Lines 105–106: This loop removes and prints all values in a heap using the remove() method.
• Line 110: It creates a new array of Integers with length n.
• Line 115: It starts a timer to measure the elapsed time of the next operation.
• Line 118: It stops the timer.
• Line 119: It calculates the elapsed time in seconds.
• Line 120: It prints out the elapsed time and the number of operations per second.
• Line 122–132: These lines perform n add and remove operations on the BinaryHeap object h and measure the elapsed time.